package algorithms

import "Algorithms/util"

//$1$个细胞的生命周期是$3$小时，$1$小时分裂一次。
//求$n$小时后，容器内有多少细胞？
//请你用已经学过的递归时间复杂度的分析方法，分析一下这个递归问题
//的时间复杂度。

//复杂度分析
func CellSplit(n int) int {
	if n == 0 {
		return 1
	}
	if n == 1 {
		return 2
	}
	if n == 2 {
		return 4
	}
	return 2*CellSplit(n-1) - CellSplit(n-3)
}

//寻找和最大的子串，用递归方法
func findMaxSub(arr []int, low, high int) (rLow, rHigh, result int) {
	//停止条件：只有一个数字
	if high == low {
		return low, high, arr[low] //只有本身一个子数组,子数组之和为自己本身
	}
	mid := (low + high) / 2
	leftLow, leftHigh, leftResult := findMaxSub(arr, low, mid)                  //分解去前半段找
	rightLow, rightHigh, rightResult := findMaxSub(arr, mid+1, high)            //分解去后半段找
	crossLow, crossHigh, crossResult := findMaxCrossingSub(arr, low, mid, high) //包含中间的情况
	if leftResult >= rightResult && leftResult >= crossResult {                 //最大是左边区间
		return leftLow, leftHigh, leftResult
	} else if rightResult >= crossResult && rightResult >= leftResult { //最大是右边区间
		return rightLow, rightHigh, rightResult
	} else { //最大是中间区间
		return crossLow, crossHigh, crossResult
	}
}

//假定子数组必然包含中点的情况，找出左右索引和子数组之和
func findMaxCrossingSub(arr []int, low, mid, high int) (maxLeft, maxRight, result int) {
	leftSum := util.INT_MIN
	sum := 0
	//遍历左边找到最大子数组和
	for i := mid; i >= low; i-- {
		sum = sum + arr[i]
		if sum > leftSum {
			leftSum = sum
			maxLeft = i
		}
	}
	rightSum := util.INT_MIN
	sum = 0
	//遍历右边找到最大子数组和
	for i := mid + 1; i <= high; i++ {
		sum = sum + arr[i]
		if sum > rightSum {
			rightSum = sum
			maxRight = i
		}
	}
	return maxLeft, maxRight, leftSum + rightSum
}

func climbStairs(n int) int {
	if n==1{
		return 1
	}
	if n==2{
		return 2
	}
	return climbStairs(n-1)+climbStairs(n-2)
}
func climbStairs2(n int) int {
	if n==1{
		return 1
	}
	if n==2{
		return 2
	}
	a,b:=1,2
	for i:=3;i<=n;i++{
		tmp:=a+b
		a,b=b,tmp
	}
	return a
}

